package codetop.microsoft.T142;

import util.ListNode;

/**
 * @Author: 18362
 * @Create: 2022-08-14 11:19:55 星期日
 */
class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        do {
            if (fast != null)
                fast = fast.next;
            else
                break;
            if (fast != null)
                fast = fast.next;
            else
                break;
            if (slow != null)
                slow = slow.next;
        } while (slow != fast);
        if (slow != fast)
            return null;
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}